package org.example.myleet.backtrack;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.Parser;

import java.math.BigInteger;
import java.util.*;

public class BacktrackSolution {

    //p37
    public void solveSudoku(char[][] board) {
        //逐行扫描找到第一个'.'，以开始进行递归回溯查找
        int nextR = -1;
        int nextC = -1;
        tag:
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    nextR = i;
                    nextC = j;
                    break tag;
                }
            }
        }
        //初始位置找到，开始逐个数字尝试
        for (char x = '1'; x <= '9'; ++x) {
            board[nextR][nextC] = x;
            boolean valid = backtrack37(board, nextR, nextC);
            if (valid) {
                return;
            }
        }
    }
    /**
     * BFS+回溯算法，在每个位置上尽力尝试
     */
    private boolean backtrack37(char[][] board, int r, int c) {
        if (!valid(board, r, c)) {
            //r行c列的数字存在重复，无效
            return false;
        }
        //有效，则在r行开始逐行扫描找出下一个'.'，以继续搜索
        int nextR = -1;
        int nextC = -1;
        tag:
        for (int i = r; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    nextR = i;
                    nextC = j;
                    break tag;
                }
            }
        }
        if (nextR == -1) {
            //没有找到'.'，说明整个board的搜索已经完成，且得到一个有效的数独结果
            return true;
        }
        //存在下一个'.'
        for (char x = '1'; x <= '9'; ++x) {
            //用1～9对该位置进行尝试
            board[nextR][nextC] = x;
            boolean valid = backtrack37(board, nextR, nextC);
            if (valid) {
                //如果递归结果是有效的，说明完成搜索，且得到一个有效的数独结果
                return true;
            }
        }
        //r行c列位置已经对1～9进行尝试，但均以失败告终，说明是前面某个位置的数字填写是不正确的，回溯，重新变成'.'，并回到上一层状态
        board[nextR][nextC] = '.';
        return false;
    }
    /**
     * 判断board中，r行c列的数字是否有效，按照数独规则就是r行、c列以及r行c列所在的小九宫格数字不会重复
     */
    private boolean valid(char[][] board, int r, int c) {
        char number = board[r][c];
        //检查一列中是否有重复
        for (int i = 0; i < 9; ++i) {
            if (i != r && number == board[i][c]) {
                return false;
            }
        }
        //检查一行中是否有重复
        for (int j = 0; j < 9; ++j) {
            if (j != c && number == board[r][j]) {
                return false;
            }
        }
        //检查r、c所在九宫格中是否有重复
        int r_ = r / 3 * 3;
        int c_ = c / 3 * 3;
        for (int i = r_; i < r_ + 3; ++i) {
            for (int j = c_; j < c_ + 3; ++j) {
                if (i != r && j != c && number == board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    //剑指Offer 38
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        List<Character> allChars = new ArrayList<>(chars.length);
        for (int i = 0; i < chars.length; ++i) {
            allChars.add(chars[i]);
        }
        //先进行字符升序排序，使相同的字符能够挨到一起，有利于剪枝
        allChars.sort(Comparator.comparingInt(c -> c));
        Set<String> result = new HashSet<>();
        backtrackOffer38(allChars, new StringBuilder(), result);
        return result.toArray(new String[0]);
    }
    private void backtrackOffer38(List<Character> allChars, StringBuilder candidate, Set<String> result) {
        if (allChars.isEmpty()) {
            result.add(candidate.toString());
            return;
        }
        for (int i = 0; i < allChars.size(); ++i) {
            Character c = allChars.get(i);
            if (i > 0 && allChars.get(i - 1).equals(c)) {
                //剪枝优化
                //例如aab，第一个a已经做过一次全排列，轮到第二个a的时候，其实情形是一样的，因此可以跳过这种情形，直接进入下一个字符的排列讨论
                continue;
            }
            candidate.append(c);
            //1、已选c，将其先移除（也可以使用boolean数组标记已经访问过）
            allChars.remove(i);
            //2、进入下一层讨论情形
            backtrackOffer38(allChars, candidate, result);
            //3、回溯
            //移除刚刚访问完的情形
            candidate.deleteCharAt(candidate.length() - 1);
            //将字符放回去，下一回合讨论下一个字符的情形（也可以使用boolean数组标记未访问过）
            allChars.add(i, c);
        }
    }

    /**
     * 40【回溯+计数】组合总和 II
     */
    private List<List<Integer>> answer40;
    private void backtrack40(int[] candidateCnt, int target, int i, List<Integer> comb, int sum) {
        if (sum > target) return;
        if (sum == target) {
            List<Integer> cp = new ArrayList<>(comb);
            answer40.add(cp);
            return;
        }
        while (i < candidateCnt.length && candidateCnt[i] < 1) ++i;
        if (i >= candidateCnt.length) return;
        //跳过，不选当前的数字i
        backtrack40(candidateCnt, target, i + 1, comb, sum);
        //下面选择当前数字i，一次处理j个数字的情况
        for (int j = 1; j <= candidateCnt[i]; ++j) {
            comb.add(i);
            backtrack40(candidateCnt, target, i + 1, comb, sum + j * i);
        }
        for (int k = 0; k < candidateCnt[i]; ++k) {
            comb.remove(comb.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int[] numCnt = new int[51];
        int sum = 0;
        for (int num : candidates) {
            sum += num;
            if (num <= target && numCnt[num] * num < target) {
                numCnt[num]++;
            }
        }
        if (sum < target) return new LinkedList<>();
        answer40 = new LinkedList<>();
        backtrack40(numCnt, target, 0, new ArrayList<>(), 0);
        return answer40;
    }

    //p46. 全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack46(result, combination, nums, visited);
        return result;
    }
    private void backtrack46(List<List<Integer>> result, List<Integer> combination, int[] nums, boolean[] visited) {
        if (combination.size() == nums.length) {
            result.add(new ArrayList<>(combination));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (!visited[i]) {
                combination.add(nums[i]);
                visited[i] = true;
                backtrack46(result, combination, nums, visited);
                combination.remove(combination.size() - 1);
                visited[i] = false;
            }
        }
    }

    /**
     * 51【回溯】N 皇后
     */
    private String[] P = new String[]{"", ".", "..", "...", "....", ".....", "......", ".......", "........"};
    private Map<String, List<String>> answerMap51;
    private boolean isValid51(int n, List<String> grid, int i, int j) {
        for (int r = i - 1; r >= 0; --r) {
            int c = j - i + r;
            if (c >= 0 && 'Q' == grid.get(r).charAt(c)) return false;
            if ('Q' == grid.get(r).charAt(j)) return false;
            c = j + i - r;
            if (c < n && 'Q' == grid.get(r).charAt(c)) return false;
        }
        return true;
    }
    //已确认i行有效
    private void backtrack51(int n, List<String> grid, int i) {
        if (i >= n - 1) {
            String all = String.join("", grid);
            if (!answerMap51.containsKey(all)) {
                answerMap51.put(all, new ArrayList<>(grid));
            }
            return;
        }
        for (int c = 0; c < n; ++c) {
            String row = P[c] + "Q" + P[n - 1 - c];
            grid.add(row);
            if (isValid51(n, grid, i + 1, c)) {
                backtrack51(n, grid, i + 1);
            }
            grid.remove(i + 1);
        }
    }
    public List<List<String>> solveNQueens(int n) {
        answerMap51 = new HashMap<>();
        List<String> grid = new ArrayList<>(n);
        for (int c = 0; c < n; ++c) {
            String row = P[c] + "Q" + P[n - 1 - c];
            grid.add(row);
            backtrack51(n, grid, 0);
            grid.remove(0);
        }
        return new ArrayList<>(answerMap51.values());
    }

    /**
     * 77【回溯】组合
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        backtrack77(result, combination, n, k, 1);
        return result;
    }
    private void backtrack77(List<List<Integer>> result, List<Integer> combination, int n, int k, int x) {
        if (combination.size() == k) {
            result.add(new ArrayList<>(combination));
            return;
        }
        if (x > n) {
            return;
        }
        for (int i = x; i <= n; ++i) {
            combination.add(i);
            backtrack77(result, combination, n, k, i + 1);
            combination.remove(combination.size() - 1);
        }
    }

    /**
     * 282【回溯】给表达式添加运算符
     */
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        backtrack282(num, target, 0, new StringBuilder(), result);
        return result;
    }
    private void backtrack282(String num, int target, int idx, StringBuilder formula, List<String> result) {
        if (idx >= num.length()) {
            try {
                long answer = computeFormula282(formula);
                if (answer == (long) target) {
                    result.add(formula.toString());
                }
            } catch (Exception e) {
                //do nothing
//                System.out.println(e.getMessage());
            }
            return;
        }
        char c = num.charAt(idx);
        formula.append(c);
        if (idx < num.length() - 1) {
            formula.append('+');
            backtrack282(num, target, idx + 1, formula, result);
            formula.deleteCharAt(formula.length() - 1);
            formula.append('-');
            backtrack282(num, target, idx + 1, formula, result);
            formula.deleteCharAt(formula.length() - 1);
            formula.append('*');
            backtrack282(num, target, idx + 1, formula, result);
            formula.deleteCharAt(formula.length() - 1);
        }
        backtrack282(num, target, idx + 1, formula, result);
        formula.deleteCharAt(formula.length() - 1);
    }
    private long computeFormula282(StringBuilder formula) {
        Queue<Object> stack = new LinkedList<>();
        StringBuilder numberStrBuilder = new StringBuilder();
        int i = 0;
        char c = formula.charAt(i++);
        while (i < formula.length() && Character.isDigit(c)) {
            numberStrBuilder.append(c);
            c = formula.charAt(i++);
        }
        if (numberStrBuilder.length() > 1 && numberStrBuilder.charAt(0) == '0') {
            throw new RuntimeException(formula.toString() + "不是一个正常的等式");
        }
        for (;;) {
            if (Character.isDigit(c)) {
                if (numberStrBuilder.length() > 0 && numberStrBuilder.charAt(0) == '0') {
                    throw new RuntimeException(formula.toString() + "不是一个正常的等式");
                }
                numberStrBuilder.append(c);
            } else {
                if (c == '+' || c == '-') {
                    stack.offer(Long.valueOf(numberStrBuilder.toString()));
                    stack.offer(c);
                    numberStrBuilder = new StringBuilder();
                } else if (c == '*') {
                    Long number1 = Long.valueOf(numberStrBuilder.toString());
                    StringBuilder number2StrBuilder = new StringBuilder();
                    do {
                        c = formula.charAt(i++);
                        if (!Character.isDigit(c)) {
                            --i;
                            break;
                        }
                        number2StrBuilder.append(c);
                    } while (i < formula.length());
                    if (number2StrBuilder.length() > 1 && number2StrBuilder.charAt(0) == '0') {
                        throw new RuntimeException(formula.toString() + "不是一个正常的等式");
                    }
                    Long number2 = Long.valueOf(number2StrBuilder.toString());
                    number1 = number1 * number2;
                    numberStrBuilder = new StringBuilder(number1.toString());
                }
            }
            if (i >= formula.length()) {
                break;
            }
            c = formula.charAt(i++);
        }
        Long number1 = Long.valueOf(numberStrBuilder.toString());
        stack.offer(number1);
        number1 = (Long) stack.poll();
        while (stack.size() > 1) {
            Object o = stack.poll();
            char operand = (char) o;
            Long number2 = (Long) stack.poll();
            if (operand == '+') {
                number1 = number1 + number2;
            } else {
                number1 = number1 - number2;
            }
        }
        return number1;
    }

    /**
     * 301【回溯】删除无效的括号
     * 思路：回溯，对每个括号是否入选结果字符串进行尝试
     * 复杂度考虑，题目要求括号不多于20个，是因为最大复杂度控制在2^20，大概100多万，是可以在1s内算完的
     * 长度不超过25，说明可以用一个数组代表map记录字符串长度集合，用set去除重复字符串即可
     */
    public List<String> removeInvalidParentheses(String s) {
        int maxLen = 0;
        HashSet<String>[] map = new HashSet[26];
        for (int i = 0; i < 26; ++i) {
            map[i] = new HashSet<>();
        }
        backtrack301(s, 0, new StringBuilder(), 0, map, maxLen);
        return new ArrayList<>(map[maxLen]);
    }
    /**
     * DFS回溯
     * @param s 初始字符串
     * @param idx 初始字符串的位置
     * @param sb StringBuilder
     * @param balance 括号平衡值
     * @param map 结果集合
     */
    private void backtrack301(String s, int idx, StringBuilder sb, int balance, HashSet<String>[] map, int maxLen) {
        if (idx >= s.length()) {
            //结束条件，idx到达字符串末尾
            if (balance == 0) {
                //如果括号平衡，说明是一种方案
                String sbs = sb.toString();
                if (maxLen < sbs.length()) {
                    //更新最大长度（即括号的最小删除数量）
                    maxLen = sbs.length();
                }
                map[sbs.length()].add(sbs);
            }
            return;
        }
        //复制一个括号平衡值
        int copyBalance = balance;
        //idx位置的字符
        char c = s.charAt(idx);
        //记录是否有连接当前字符
        boolean appended = false;
        //下面先尝试连接字符，再尝试不连接字符
        if (c == '(') {
            //遇到左括号，平衡值-1，并连接该括号
            --balance;
            sb.append(c);
            appended = true;
        } else if (c == ')') {
            if (balance < 0) {
                //右括号在平衡值为负的时候才合法，才能连接
                ++balance;
                sb.append(c);
                appended = true;
            }
        } else {
            //非括号的直接连接
            sb.append(c);
            appended = true;
        }
        if (appended) {
            //有连接的情况，递归
            backtrack301(s, idx + 1, sb, balance, map, maxLen);
            //有连接的情况，回溯，尝试删除当前字符，即制造不选当前字符的情况
            sb.deleteCharAt(sb.length() - 1);
        }
        //尝试不选当前字符的情况
        backtrack301(s, idx + 1, sb, copyBalance, map, maxLen);
    }

    /**
     * 306【回溯】累加数
     */
    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) {
            //不够长度
            return false;
        }
        for (int i = 1; i <= num.length(); ++i) {
            String num1Str = num.substring(0, i);
            if (num1Str.length() > 1 && num1Str.charAt(0) == '0') {
                //过滤00这种数字
                continue;
            }
            BigInteger num1 = new BigInteger(num.substring(0, i));
            for (int j = i + 1; j <= num.length(); ++j) {
                String num2Str = num.substring(i, j);
                if (num2Str.length() > 1 && num2Str.charAt(0) == '0') {
                    //过滤00这种数字
                    continue;
                }
                BigInteger num2 = new BigInteger(num2Str);
                if (j == num.length()) {
                    //整个num被分割成num1和num2，后门没数字了，也不考虑这种情况
                    continue;
                }
                if (isAdditive306(num, num1, num2, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean isAdditive306(String num, BigInteger num1, BigInteger num2, int startIdx) {
        if (startIdx == num.length()) {
            //成功扫描到结尾，验证是累加数字
            return true;
        }
        //累加出下一个数字
        BigInteger num3 = num1.add(num2);
        String num3s = num3.toString();
        if (num.length() - startIdx < num3s.length()) {
            //剩余数字位数小于累加的数字的长度，不进行下一步寻找
            return false;
        }
        int idx = startIdx;
        //比较累加出的数字是否在startIdx处出现
        for (int i = 0; i < num3s.length(); ++i) {
            char num3sc = num3s.charAt(i);
            char numc = num.charAt(idx);
            if (num3sc != numc) {
                //累加出的数字与startIdx处的数不同，不进行下一步寻找
                return false;
            }
            ++idx;
        }
        //递归进行下一步查找
        return isAdditive306(num, num2, num3, idx);
    }

    //p1238
    public List<Integer> circularPermutation(int n, int start) {
        int targetSize = (int) Math.pow(2, n);
        List<Integer> answer = new ArrayList<>(targetSize);
        answer.add(start);
        Set<Integer> visited = new HashSet<>(targetSize);
        visited.add(start);
        backtrack1238(answer, visited, targetSize, start, n);
        return answer;
    }
    private boolean backtrack1238(List<Integer> answer, Set<Integer> visited, int targetSize, int start, int n) {
        int cur = answer.get(answer.size() - 1);
        if (targetSize == answer.size()) {
            int a = Math.max(start, cur);
            int b = Math.min(start, cur);
            int c = a - b;
            if (c == 0) return false;
            return Integer.bitCount(c) == 1;
        }
        for (int i = 0; i < n; ++i) {
            int mask = 1 << i;
            int next = (cur & mask) > 0 ? (cur - mask) : (cur + mask);
            if (!visited.contains(next)) {
                answer.add(next);
                visited.add(next);
                if (backtrack1238(answer, visited, targetSize, start, n)) {
                    return true;
                }
                answer.remove(answer.size() - 1);
                visited.remove(next);
            }
        }
        return false;
    }

    //p1255
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        //记录每个单词的分数
        int[] wordScores = new int[words.length];
        for (int i = 0; i < words.length; ++i) {
            int wordScore= 0;
            for (char ch : words[i].toCharArray()) {
                wordScore += score[ch - 'a'];
            }
            wordScores[i] = wordScore;
        }
        //记录每个字母剩余的可用数量
        Map<Character, Integer> letterCount = new HashMap<>(26);
        for (char ch : letters) {
            letterCount.put(ch, letterCount.getOrDefault(ch, 0) + 1);
        }
        //回溯
        return backtrack1255(words, wordScores, letterCount, 0, 0);
    }
    private int backtrack1255(String[] words, int[] wordScores, Map<Character, Integer> letterCount, int curScore, int i) {
        if (i >= words.length) {
            //遍历完成所有单词，返回最大分数
            return curScore;
        }
        int max = curScore;
        //计算单词所需字母
        String word = words[i];
        Map<Character, Integer> wordLetterCount = new HashMap<>(26);
        for (char ch : word.toCharArray()) {
            wordLetterCount.put(ch, wordLetterCount.getOrDefault(ch, 0) + 1);
        }
        //计算单词所需字母在当前状态是否满足
        boolean meet = true;
        for (char ch : wordLetterCount.keySet()) {
            if (letterCount.getOrDefault(ch, 0) < wordLetterCount.get(ch)) {
                meet = false;
                break;
            }
        }
        if (meet) {
            //扣减字母数量，加上分数
            for (char ch : wordLetterCount.keySet()) {
                letterCount.put(ch, letterCount.get(ch) - wordLetterCount.get(ch));
            }
            max = backtrack1255(words, wordScores, letterCount, curScore + wordScores[i], i + 1);
            //回溯，退回状态
            for (char ch : wordLetterCount.keySet()) {
                letterCount.put(ch, letterCount.get(ch) + wordLetterCount.get(ch));
            }
        }
        //不选用这第i个单词
        max = Math.max(max, backtrack1255(words, wordScores, letterCount, curScore, i + 1));
        return max;
    }

    //p1774
    private int p1774MinPrice;
    private Map<Integer, Integer> statusMapPrice;
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        p1774MinPrice = Integer.MAX_VALUE / 2;
        statusMapPrice = new HashMap<>();
        for (int i = 0; i < baseCosts.length; ++i) {
            p1774Backtrack(toppingCosts, 0, baseCosts[i], target);
        }
        return p1774MinPrice;
    }
    private void p1774Backtrack(int[] toppingCosts, int p, int curCost, int target) {
        if (Math.abs(p1774MinPrice - target) < curCost - target) {
            return;
        } else if (Math.abs(p1774MinPrice - target) >= Math.abs(curCost - target)) {
            if (Math.abs(p1774MinPrice - target) > Math.abs(curCost - target)) {
                p1774MinPrice = curCost;
            } else {
                p1774MinPrice = Math.min(p1774MinPrice, curCost);
            }
        }
        if (p == toppingCosts.length) {
            return;
        }
        p1774Backtrack(toppingCosts, p + 1, curCost + toppingCosts[p] * 2, target);
        p1774Backtrack(toppingCosts, p + 1, curCost + toppingCosts[p], target);
        p1774Backtrack(toppingCosts, p + 1, curCost, target);
    }

    //p2044
    private int count2044;

    public int countMaxOrSubsets(int[] nums) {
        int maxOr = 0;
        for (int num : nums) {
            maxOr = maxOr | num;
        }
        count2044 = 0;
        backtrack2044(nums, 0, 0, maxOr);
        return count2044;
    }

    private void backtrack2044(int[] numbers, int i, int orResult, int target) {
        if (i >= numbers.length) {
            if (orResult == target) {
                ++count2044;
            }
            return;
        }
        backtrack2044(numbers, i + 1, orResult, target);
        int newOrResult = orResult | numbers[i];
        backtrack2044(numbers, i + 1, newOrResult, target);
    }

    /**
     * 2056【回溯】棋盘上有效移动组合的数目
     */
    private static final int[][] B_DIRS = new int[][]{{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
    private static final int[][] R_DIRS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static final int[][] Q_DIRS = new int[][]{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    private static int[][] getDirs2056(String piece) {
        char c = piece.charAt(0);
        if ('b' == c) return B_DIRS;
        else if ('r' == c) return R_DIRS;
        else return Q_DIRS;
    }
    // 判断两个移动是否合法，即不存在同一时刻两个棋子重叠的情况
    private boolean isValid2056(int[] m1, int[] m2) {
        int x1 = m1[0], y1 = m1[1]; // 初始位置
        int x2 = m2[0], y2 = m2[1];
        for (int i = 0; i < Math.max(m1[4], m2[4]); i++) {
            // 每一秒走一步
            if (i < m1[4]) {
                x1 += m1[2];
                y1 += m1[3];
            }
            if (i < m2[4]) {
                x2 += m2[2];
                y2 += m2[3];
            }
            if (x1 == x2 && y1 == y2) { // 重叠
                return false;
            }
        }
        return true;
    }
    private int dfs2056(int n, int p, int[][][] allMoves, int[][] path) {
        if (n == p) return 1;
        int res = 0;
        outer:
        for (int[] move : allMoves[p]) {
            for (int j = 0; j < p; ++j) {
                if (!isValid2056(move, path[j])) {
                    continue outer;
                }
            }
            path[p] = move;
            res += dfs2056(n, p + 1, allMoves, path);
        }
        return res;
    }
    private int[][] generateMoves(String piece, int[] position) {
        int[][] dirs = getDirs2056(piece);
        List<int[]> moves = new ArrayList<>();
        moves.add(new int[]{position[0], position[1], 0, 0, 0}); //原地不动
        for (int[] dir : dirs) {
            int step = 1, dx = dir[0], dy = dir[1];
            int r = position[0] + dx, c = position[1] + dy;
            while (1 <= r && r <= 8 && 1 <= c && c <= 8) {
                moves.add(new int[]{position[0], position[1], dir[0], dir[1], step});
                ++step;
                r += dir[0];
                c += dir[1];
            }
        }
        int[][] moveArr = new int[moves.size()][];
        for (int i = 0; i < moves.size(); ++i) {
            moveArr[i] = moves.get(i);
        }
        return moveArr;
    }
    public int countCombinations(String[] pieces, int[][] positions) {
        int n = pieces.length;
        int bi = 0, ri = 0;
        int[][][] allMoves = new int[n][][];
        for (int i = 0; i < n; ++i) {
            allMoves[i] = generateMoves(pieces[i], positions[i]);
        }
        int[][] path = new int[n][];
        return dfs2056(n, 0, allMoves, path);
    }

    /**
     * 2698【回溯】求一个整数的惩罚数
     */
    public int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            int pow = i * i;
            if (isPunishmentNumber(i, pow + "", 0)) {
                //其实惩罚数是固定存在的，可以一次性求出n内所有的惩罚数，然后提交答案的时候打表
//                System.out.printf("%d, ", i);
                sum += pow;
            }
        }
        return sum;
    }
    private boolean isPunishmentNumber(int target, String remain, int sum) {
        if (sum > target) return false;
        //如果remain已经没有了，且恰好target==sum，就算找到一个惩罚数
        if (remain.length() < 1 && target == sum) return true;
        for (int i = 1; i <= remain.length(); ++i) {
            //将remain逐位拆分成两部分，一部分是这个加到sum里面的数，另一部分是继续DFS回溯的部分
            int num = Integer.parseInt(remain.substring(0, i));
            if (num <= target) {
                if (isPunishmentNumber(target, remain.substring(i), sum + num)) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        BacktrackSolution solution = new BacktrackSolution();
        System.out.println(solution.combinationSum2(new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 27));
        System.out.println(solution.combinationSum2(new int[]{14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12}, 27));
        System.out.println(solution.combinationSum2(new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 27));
        System.out.println(solution.combinationSum2(new int[]{2,5,2,1,2}, 5));
//        Assert.isTrue(12 == solution.countCombinations(new String[]{"bishop"}, Parser.parse("[[4,3]]")));
    }
}
